package com.cn.algorithm02.class04;

import java.util.Stack;

/***
 * @author: hels
 * @description: 设计一个栈，可以返回最小元素，可以使用现存栈，要求时间复杂度O(1)
 * 思路： 准备两个栈，一个是数据栈，另一个是最小值栈，两个栈数据同步push，第一次添加都直接放入，后续数字个最小栈顶比较，新元素<=放入，否则
 * 重复放入栈顶元素。删除时
 **/
public class C04_MinOfStack {
    Stack<Integer> dataStack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();

    public static void main(String[] args) {
        C04_MinOfStack myStack = new C04_MinOfStack();
        myStack.push(7);
        myStack.push(6);
        myStack.push(6);
        myStack.push(5);
        myStack.push(8);
        System.out.println(myStack.dataStack);
        System.out.println(myStack.minStack);
        System.out.println(myStack.getMin());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.dataStack);
        System.out.println(myStack.minStack);

    }

    // push ： 两种size=0，和size >0
    public void push(Integer i) {
        if (dataStack.size() == 0) {
            minStack.push(i);
        } else {
            Object o = i.compareTo(minStack.peek()) == 1 ? minStack.push(minStack.peek()) : minStack.push(i);
        }
        dataStack.push(i);
    }

    // pop 同步弹出
    public Integer pop() {
        minStack.pop();
        return dataStack.pop();
    }

    // getMin
    public Integer getMin() {
        return minStack.peek();
    }
}
